package countPairs;

import java.util.Comparator;
import java.util.List;

public class Solution {
    public int countPairs(List<Integer> nums, int target) {
        nums.sort((o1, o2) -> o1 - o2);
        Integer[] arr = nums.toArray(new Integer[nums.size()]);
        int ans = 0;
        // System.out.println(nums);
        for (int i = 0; i < nums.size(); i++) {
            int t = binarySearch(arr,i+1,nums.size()-1,target - nums.get(i));
            //  System.out.println(t);
            ans+=t;
        }
        return ans;
    }
    // 1 1 2 3 4 5 6 7 7 8 9    5
    private int binarySearch(Integer[] nums,int l,int r,int target) {
        int star = l;
        while (l<=r) {
            int mid = (l+r)/2;
            if(nums[mid]<target) {
                l = mid+1;
            }else {
                r = mid-1;
            }
        }
        return l - star;
    }
}
